It is known that a large group of multistage packet-switching interconnection networks includes networks comprising a plurality of identical elements connected so that any network output may be reached from any input. Examples of such networks are the so called omega, delta and Benes networks. In case of self-routing networks, the network elements are to:
analyze the tag identifying a packet destination and consequently route the packet towards the appropriate output;
solve possible routing conflicts; and
buffer packets which cannot be immediately forwarded because of routing conflicts or unavailability of the subsequent network stage or of the destination device.
The latter function will be generally performed so as to set an upper limit to packet residence time in the network. This increases network efficiency.
In some applications, for instance within parallel processing structures implementing distributed algorithms or in telecommunications networks, other functions appear desirable, such as the capability of broadcasting the same message to a plurality of destinations, so that connection of one element input with a plurality of outputs must be possible.
A network consisting of elements having also that further capability is disclosed by H. J. Siegel and R. J. McMillen in the article "The multistage cube: a versatile interconnection network", IEEE Computer, December 1981, pages 65-76. That network consists of elements with two inputs and two outputs, comprising each a switch with a control unit that, on the basis of the information contained in the routing tag, sets up the appropriate connections of one input with one or more outputs. In the latter case, the connection may be set up either with two outputs whose addresses are in a given relationship, or with a greater number of outputs, provided that such a number is a power of 2. This implies that, in each network stage, all elements traversed by a message must have the same configuration. This limits the network efficiency, as a number of destination devices might receive no information or information which is not of interest and is then to be eliminated.
Moreover the article does not indicate how internal blocking of the network can be avoided in the case of information broadcasting or how an upper limit can be set to the residence time in the network.